package main.java.indi.zyj.coderecord;

public class FindRedundantConnection {

    int[] father;
    public int[] findRedundantConnection(int[][] edges) {

        father = new int[1000];
        int[] res = new int[2];
        init();

        for (int i = 0; i < edges.length; i++) {
            if (!isSame(edges[i][0], edges[i][1])){
                join(edges[i][0], edges[i][1]);
            } else {
                res = edges[i];
            }

        }

        return res;

    }

    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    public int find(int u) {
        if (father[u] == u) {
            return u;
        } else {
            father[u] = find(father[u]);
        }
        return father[u];
    }

    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return;
        }
        father[v] = u;
    }

}
